package 中等.模拟;

import java.util.Arrays;

/**
 * 给你一个数组 towers 和一个整数 radius 。
 * 数组  towers  中包含一些网络信号塔，其中 towers[i] = [xi, yi, qi]
 * 表示第 i 个网络信号塔的坐标是 (xi, yi) 且信号强度参数为 qi 。所有坐标
 * 都是在  X-Y 坐标系内的 整数 坐标。两个坐标之间的距离用 欧几里得距离 计算。
 * 整数 radius 表示一个塔 能到达 的 最远距离 。如果一个坐标跟塔的距离在
 * radius 以内，那么该塔的信号可以到达该坐标。在这个范围以外信号会很微弱，
 * 所以 radius 以外的距离该塔是 不能到达的 。
 * 如果第 i 个塔能到达 (x, y) ，那么该塔在此处的信号为 ⌊qi / (1 + d)⌋ ，
 * 其中 d 是塔跟此坐标的距离。一个坐标的 信号强度 是所有 能到达 该坐标的
 * 塔的信号强度之和。
 * 请你返回数组 [cx, cy] ，表示 信号强度 最大的 整数 坐标点 (cx, cy) 。
 * 如果有多个坐标网络信号一样大，请你返回字典序最小的 非负 坐标。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/coordinate-with-maximum-network-quality/
 */
public class 网络信号最好的坐标_1620 {

    public static void main(String[] args) {

        System.out.println(Arrays.toString(bestCoordinate(new int[][]{{1, 2, 5}, {2, 1, 7}, {3, 1, 9}}, 2)));

    }

    /**
     * 遍历获取每个位置的信号和
     *
     * @param towers
     * @param radius
     * @return
     */
    public static int[] bestCoordinate(int[][] towers, int radius) {
        int[] ans = new int[2];
        if (towers.length == 1 && towers[0][2] == 0) {
            return ans;
        }
        ans[0] = towers[0][0];
        ans[1] = towers[0][1];
        int maxSignal = 0;

        for (int x = 0; x <= 50; x++) {
            for (int y = 0; y <= 50; y++) {
                int curSignal = 0;
                for (int j = 0; j < towers.length; j++) {
                    int d2 = (x - towers[j][0]) * (x - towers[j][0]) + (y - towers[j][1]) * (y - towers[j][1]);
                    // 先不开根号，否则有精度损失
                    if (d2 <= radius * radius) {
                        // 注意：指的是发出信息的位置的信号参数
                        curSignal += (int) Math.floor(towers[j][2] / (1 + Math.sqrt(d2)));
                    }
                }

                // 因为 x y 是从小往大遍历，无需判断 curSignal=maxSignal 时选择字典序较小的
                if (curSignal > maxSignal) {
                    maxSignal = curSignal;
                    ans[0] = x;
                    ans[1] = y;
                }
            }
        }

        return ans;
    }

}
